#!/usr/bin/env python
# -*- coding: utf-8 -*-
#

class Node:
    def __init__(self, prev, me):
        self.prev = prev
        self.me = me
        self.next = None

#Implementation of a length-limited O(1) LRU cache
class LRU: 
    def __init__(self, count):
        self.count = max(count, 2)
        self.d = {}
        self.first = None
        self.last = None

    def __contains__(self, obj):
        return obj in self.d
        #a = self.d[obj].me
        #self[a[0]] = a[1]
        #return a[1]

    def __getitem__(self, obj):
        return self.d[obj].me[1]

    def __setitem__(self, obj, val):
        if obj in self.d:
            del self[obj]
        nobj = Node(self.last, (obj, val))
        if self.first is None:
            self.first = nobj
        if self.last:
            self.last.next = nobj
        self.last = nobj
        self.d[obj] = nobj
        if len(self.d) > self.count:
            if self.first == self.last:
                self.first = None
                self.last = None
                return
            a = self.first
            a.next.prev = None
            self.first = a.next
            a.next = None
            del self.d[a.me[0]]
            del a

    def __delitem__(self, obj):
        nobj = self.d[obj]
        if nobj.prev:
            nobj.prev.next = nobj.next
        else:
            self.first = nobj.next
        if nobj.next:
            nobj.next.prev = nobj.prev
        else:
            self.last = nobj.prev
        del self.d[obj]

    def __iter__(self):
        cur = self.first
        while cur != None:
            cur2 = cur.next
            yield cur.me[1]
            cur = cur2
        raise StopIteration

    def iteritems(self):
        cur = self.first
        while cur != None:
            cur2 = cur.next
            yield cur.me
            cur = cur2
        raise StopIteration

    def iterkeys(self):
        return iter(self.d)

    def itervalues(self):
        for i,j in self.iteritems():
            yield j

    def keys(self):
        return [i for i,j in self.iteritems()]

    def values(self):
        return [j for i,j in self.iteritems()]

    def items(self):
        return [i for i in self.iteritems()]

    def __repr__(self):
        """representation. for debug only, do not affect LRU
        """
        x =''
        for k,v in self.d.items():
            if x :
                x = '%s, %s:%s' % (x, k.__repr__(), v.me[1].__repr__())
            else :
                x = '%s:%s' % (k.__repr__(), v.me[1].__repr__())
        return '{%s}' % x


def test():
    cache = LRU(2)

    cache['stuff'] = 'hehe'
    cache['asdf'] = '231'
    cache['333'] = '123'
    print 'stuff' in cache
    print '333' in cache
    print cache

if __name__ == '__main__':
    test()

